﻿
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

/*
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。
请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
 
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
*/


//二分解法
//class Solution {
//public:
//	int diff = 9999999;
//	int ans = 0;
//	int Check(vector<int>& nums, int start, int find) {
//		int ret = -1;
//		if (start >= nums.size()) return ret;
//		int l = start; int r = nums.size() - 1;
//		while (l < r) {
//			int mid = (l + r) >> 1;
//			if (nums[mid] >= find) r = mid;
//			else l = mid + 1;
//		}
//
//		if (diff > abs(nums[l] - find)) {
//			diff = abs(nums[l] - find); ret = l;
//		}
//		if (l > start && diff > abs(nums[l-1] - find)) {
//			diff = abs(nums[l-1] - find); ret = l-1;
//		}
//
//		return ret;
//	}
//
//	int threeSumClosest(vector<int>& nums, int target) {
//		sort(nums.begin(), nums.end());
//		for (int i = 0; i < nums.size(); i++) {
//			for (int j = i+1; j < nums.size(); j++) {
//				int find = target - nums[i] - nums[j];
//				int ret = Check(nums,j+1,find);
//				if (-1 != ret) ans = nums[i] + nums[j] + nums[ret];
//			}
//		}
//		return ans;
//	}
//};



//双指针
class Solution {
public:
	int ans = 9999999;
	int threeSumClosest(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++) {
			int l = i + 1; int r = nums.size() - 1;
			while (l < r) {
				int sum = nums[i] + nums[l] + nums[r];
				if (abs(ans - target) > abs(sum - target)) { ans = sum; }
				if (sum > target) { r--; }
				else if (sum < target) { l++; }
				else { return sum; }
			}
		}
		return ans;
	}
};



/*
int main()
{
	Solution s;
	vector<int> v{ -1,0,1,1,55 };
	cout << s.threeSumClosest(v, 3);

	return 0;
}
*/
